package com.wangyadong.hobby.schedule.jobtask.dsa.stack;

class Skiplist {
    final int HEAD_VALUE = -1; // 链表头节点的值
    final Node HEAD = new Node(HEAD_VALUE);
    Node head; // 最左上角的头节点，所有操作的开始位置
    int levels; // 当前层级，即 head 节点所在的最高层数

    public Skiplist() {
        head = HEAD;
        levels = 1;
    }

    class Node {
        int val;
        Node right, down;

        Node(int val) {
            this(val, null, null);
        }

        Node(int val, Node right, Node down) {
            this.val = val;
            this.right = right;
            this.down = down;
        }
    }

    public void add(int num) { // 1.定位插入位置：原链表中 >= num 的最小节点前
        Node node = head;
        int i = 0; // 操作上述数组
        while (node != null) { // node==null，到达原链表 w
            while (node.right != null && node.right.val < num) {
                node = node.right;
            }
            if (node.down == null) {
                break;
            }
            // 继续查找下一层的位置
            node = node.down;
        }
        // 2.插入新节点
        Node newNode = new Node(num, node.right, null);
        node.right = newNode; // 3.TODO 根据扔硬币决定（是否）生成索引
    }

    public boolean search(int target) {
        Node n = head;
        while (n != null) { // 1.在同一层级上向右查找，直到链表的结尾
            while (n.right != null && n.right.val < target) {
                n = n.right;
            }// 2.若找到，返回true
            Node right = n.right; // 要查找的节点
            if (right != null && right.val == target) {
                return true;
            }// 3.若右侧数据较大，向下一层
            n = n.down;
        }
        return false;
    }

    public boolean erase(int num) {
        boolean exist = false;
        Node n = head;
        while (n != null) { // 2.获取该指定数据节点的前一个节点
            while (n.right != null && n.right.val < num) {
                n = n.right;
            }// 2.与当前层链表断开
            Node right = n.right; // 要删除的节点
            if (right != null && right.val == num) {
                n.right = right.right;
                right.right = null; // help GC
                exist = true; // 删除下一层
                n = n.down;
            }
        }
        return exist;
    }


}
